COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	%Making Computer Chess More Scientific
C00019 00003	\smallskip\centerline{Copyright \copyright\ 1989\ by John McCarthy}
C00020 ENDMK
C⊗;
%Making Computer Chess More Scientific
\input memo.tex[let,jmc]
\title{Making Computer Chess More Scientific}


\noindent Abstract:  We propose new forms of computer chess
competition to make these competitions a greater benefit to AI
science and a greater benefit to public understanding and maybe
also more entertaining.

1.  The situation

Computer chess is a little more than 30 years old.  Most strong programs of
today are mainly based on some ideas developed in the 1950s and 1960s.  These
include evaluation functions, alpha-beta search, move ordering heuristics 
including killer, opening book, transposition tables, quiescence criteria
and forced move sequences.  Some of the ideas, e.g., quiescence criteria,
are not definite in themselves--their realization is achieved in different
ways by different programs.

Other ideas are used by only a few programs.  These include strongly
selective search, elaborate pattern recognition, combining information from
separate analyses of aspects of a position, keeping lists of bad moves
(anti-killer) and the use of computer-prepared databases.

Refinements in programming techniques, advances in hardware speed and the
development of special chess-oriented parallel hardware have brought chess
programs to the point of Deep Thought's defeat of an international
grandmaster in tournament play and the use of programs by at least one
grandmaster in preparing for tournaments.

Databases have shown that chess doctrine about certain endgames need
revision.  It is unclear how much of the information in these databases can
be summarized in a way that can be learned and used by humans not using computers
or massive printouts.

It seems plausible that the known techniques together with expected advances
in hardware will make possible within the next ten years programs that can
defeat the world champion under normal match conditions.  These will
probably use special chess hardware.

When and if this occurs, a reorientation of computer chess effort will surely
occur.  Once a rating of 3,000 has been achieved, a rating of 3,500 will be
a less meaningful goal.  Human and computer tournaments will be separated.

Contrary to some expectations, I believe that interest in human chess will
continue, just as the taming of horses and the invention of bicycles and cars did
not reduce interest in human foot races.  The chess players will become
attached to computer programs for analyzing positions, for training and for
developing strategies.  Spectators will use computers to help understand
why the moves were made.

2.  The bad news

In the 1960s, Alexander Kronrod, one of the inspirers of the Soviet Kaissa
program referred to chess as the {\it Drosophila} of artificial intelligence.
{\it Drosophila} is the fruit fly that for many years has served as a major
experimental vehicle in the study of genetics.  While fruit flies are not as 
useful as elephants, a fruit fly generation is two weeks and a bottle of
convenient size can hold 1,000.

Chess has many advantages as an experimental vehicle for AI.

1.  Program performance can be compared with human performance at all levels of
human ability and experience.

2.  Chess positions provide a variety of intellectual problems requiring a
variety of intellectual mechanisms.

Unfortunately, this promise has been realized only to a small extent.

Here's why

1.  The government agencies and corporations that fund research tend to take
a short term view that emphasizes what can be done that can be claimed to
have a technological payoff in the next two years.  In the case of computer
science in general, of AI in particular and research involving chess
still more specifically, this has been made worse specific circumstances.

a.  Physicists, who have deservedly great prestige left over from World War II
are the most prestigious defenders of basic research.  They have succeeded in
getting successively more expensive particle accelerators funded without
claiming short term technological payoffs.  The superconducting supercollider
supported by the Reagan and Bush Administrations will cost as much as a fully
equipped aircraft carrier.

However, physicists take an engineering view of computer science.  They think
of computers as auxiliary tools for doing physics, controlling the experiments,
reducing data, making theoretical calculations that can be compared with
experiment and (most recently) doing ``digital physics''.  With all these
distractions, it is not surprising that basic computer science, the study
of computational processes, escapes their attention.  AI, which requires a
different methodology from the equations they like, is even more foreign to them.
Other scientists tend to take equally short range views.

b.  The idea of artificial intelligence is often subject to philosophically
motivated hostility.  It is not professional philosophers that make problems.
For every professional philosopher who considers artificial intelligence a
contradiction in terms, there is another philosopher to defend AI.  Many of
the younger philosophers have experience with using computers that reduces
tendencies to dogmatic assertions about what computers can not do or why it
does not count if they do.

I think we break even with the journalists, and their increasing experience with
computers has also helped.

The main problem has been intuitive philosophical attitudes of all kinds 
of people, e.g., congressmen, generals, corporation executives, humanist 
professors and countercultural gurus.

c.  Anything having to do with chess is subject to attack as frivolous, and 
this is decisive in many quarters, unless publicity justifies the support.
Frivolity is not considered an objection when publicity is the
motivation, because most publicity is frivolous.

I once convinced a DARPA program manager that a graduate student's thesis using
chess tactical positions to study pattern matching was scientifically worthwhile.  
``Okay'', he said, ``but when he publishes a paper about his research, would he
kindly not acknowledge our support.''  Maybe he was right to say this.  New
directors of DARPA are always looking for projects to kill to get money for
their own ideas.  Senator Proximire's staffers were looking for targets for his
golden fleece award, and no recipient of this award has ever gotten equal time
in the media to defend his research.

Nevertheless, the thesis was finished and published and so have many others using
chess as a vehicle.

I suppose Hitech and Deep Thought have escaped attack partly because they
exhibit the powers of special purpose hardware, a current enthusiasm.

d.  It is worth mentioning the 1959 IBM purge of AI research.  Between 1959 and
1983 IBM Research did nothing it called AI.  After that they had the effrontery
to call themselves leaders in the field.

Between 1956 and 1959 IBM pioneered in AI.  They did the first full board
chess program, the Geleruter plane geometry theorem prover, the Fortran List
Processing Language, and other work in theorem proving, and experiments with
computer learning.  The purged seems to have been motivated by (1)
internal power struggle.  The proponent of AI research took a leave of absence to
be a visiting professor at M.I.T. at what turned out to be the cost of his
subsequent IBM career.  (2) a vociferously ignorant and intolerant philosopher
or two (3) some image minded executive's idea that AI might be regarded by 
the public as threatening.  Doubtless, a historian could correct some of the
above by extensive interviewing, but this is unlikely to happen.

Other purges of AI research have occurred from time-to-time.  I was told of
one in the Soviet Union in the late 1970s or early 80s.

Much of the above remarks about the support of AI in general are irrelevant to 
chess research, but since I do not intend to write a separate article about the 
history of the support of AI research, I am leaving it in.

Now back to chess.

2.  Work in computer chess has had two motivations that have overshadowed
its research interest.  First, computer chess has been an exciting sport.  New
records are set all the time as performance creeps up on the chess masters.  A
one to three year time horizon is suggested by the schedule of tournaments.
Second, chess machines have become a minor but profitable commercial
product.  Neither sport nor commerce produces scientific papers as its most
important product.  Indeed both motivations encourage obscurity if not actual
secrecy about improvements.

There is also an unfortunate objective factor.  After the flurry of new ideas
of the 50s and 60s, the best competitive results have been obtained by
attention to detail in chess-specific programming and in getting more powerful
hardware.  Nobody has wiped out the competition by radically new ideas.
Fear not.  It will happen.  There is too large a gap between the efficiency
of human search of the chess move tree and the brute force used by current
programs.  Factors of thousands and even millions in search efficiency await us.

3.  Proposals for Encouraging More Science in Computer Chess

The computer chess community can not do much about governments and corporations,
but it can improve its own activities.

Here are some considerations.

1.  Maybe computer chess tournaments held according to the usual human rules are
useful.  They require no adaptation of the parts of the program designed for taking
part in human tournaments.  Maybe they also provide some training for the
programs' operators.  It also avoids worries that the rules are chosen to favor 
certain entrants.  However, they lead to the games being analyzed just as if they
were human games.  What lines the program analyzed reman unknown.


	In addition to the computer chess tournaments conducted according
to the same rules as those for humans, we propose that ICCA sponsor
some tournaments according to rules more appropriate for advancing
the AI aspects of computer chess.  Here are some suggestions.

	1. Judges will identify critical positions for analysis
and critical questions about these positions.

	Contestants will bring their favorite positions to see
which programs get the answers looking at the fewest nodes.
\smallskip\centerline{Copyright \copyright\ 1989\ by John McCarthy}
\smallskip\noindent{This draft of CHESS[S89,JMC]\ TEXed on \jmcdate\ at \theTime}
\vfill\eject\end